<!-- This comment will put IE 6, 7 and 8 in quirks mode -->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>shark::IterativeNNQuery&lt; DataContainer &gt; Class Template Reference</title>
<script type="text/javaScript" src="search/search.js"></script>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
<script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3.0.1/es5/tex-mml-chtml.js"></script>
<script src="../../mlstyle.js"></script>
<link href="../css/besser.css" rel="stylesheet" type="text/css"/>
</head>
<!-- pretty cool: each body gets an id tag which is the basename of the web page  -->
<!--              and allows for page-specific CSS. this is client-side scripted, -->
<!--              so the id will not yet show up in the served source code -->
<script type="text/javascript">
    jQuery(document).ready(function () {
        var url = jQuery(location).attr('href');
        var pname = url.substr(url.lastIndexOf("/")+1, url.lastIndexOf(".")-url.lastIndexOf("/")-1);
        jQuery('#this_url').html('<strong>' + pname + '</strong>');
        jQuery('body').attr('id', pname);
    });
</script>
<body>
    <div id="shark_old">
        <div id="wrap">
            <div id="header">
                <div id="site-name"><a href="../../sphinx_pages/build/html/index.html">Shark machine learning library</a></div>
                <ul id="nav">
                    <li >
                        <a href="../../sphinx_pages/build/html/rest_sources/installation.html">Installation</a>
                    </li>
		    <li >
                        <a href="../../sphinx_pages/build/html/rest_sources/tutorials/tutorials.html">Tutorials</a>
                    </li>
		    <li >
                        <a href="../../sphinx_pages/build/html/rest_sources/benchmark.html">Benchmarks</a>
                    </li>
                    <li class="active">
                        <a href="classes.html">Documentation</a>
                        <ul>
                            <li class="first"></li>
                            <li><a href="../../sphinx_pages/build/html/rest_sources/quickref/quickref.html">Quick references</a></li>
                            <li><a href="classes.html">Class list</a></li>
                            <li class="last"><a href="group__shark__globals.html">Global functions</a></li>
                        </ul>
                    </li>
                </ul>
            </div>
        </div>
    </div>
<div id="doxywrapper">
<!--
    <div id="global_doxytitle">Doxygen<br>Documentation:</div>
-->
    <div id="navrow_wrapper">
<!-- Generated by Doxygen 1.9.8 -->
<div id="nav-path" class="navpath">
  <ul>
<li class="navelem"><a class="el" href="namespaceshark.html">shark</a></li><li class="navelem"><a class="el" href="classshark_1_1_iterative_n_n_query.html">IterativeNNQuery</a></li>  </ul>
</div>
</div><!-- top -->
<div class="header">
  <div class="summary">
<a href="classshark_1_1_iterative_n_n_query-members.html">List of all members</a> &#124;
<a href="#nested-classes">Classes</a> &#124;
<a href="#pub-methods">Public Member Functions</a>  </div>
  <div class="headertitle"><div class="title">shark::IterativeNNQuery&lt; DataContainer &gt; Class Template Reference</div></div>
</div><!--header-->
<div class="contents">

<p>Iterative nearest neighbors query.  
 <a href="classshark_1_1_iterative_n_n_query.html#details">More...</a></p>

<p><code>#include &lt;<a class="el" href="_tree_nearest_neighbors_8h_source.html">shark/Algorithms/NearestNeighbors/TreeNearestNeighbors.h</a>&gt;</code></p>
<table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a id="pub-methods" name="pub-methods"></a>
Public Member Functions</h2></td></tr>
<tr class="memitem:a02c6b80d059c5bd4964ed64a7420ede0" id="r_a02c6b80d059c5bd4964ed64a7420ede0"><td class="memItemLeft" align="right" valign="top">&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classshark_1_1_iterative_n_n_query.html#a02c6b80d059c5bd4964ed64a7420ede0">IterativeNNQuery</a> (<a class="el" href="classshark_1_1_binary_tree.html">tree_type</a> const *tree, DataContainer const &amp;data, value_type const &amp;point)</td></tr>
<tr class="separator:a02c6b80d059c5bd4964ed64a7420ede0"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:af4917cb856b7b71d313d42978793e011" id="r_af4917cb856b7b71d313d42978793e011"><td class="memItemLeft" align="right" valign="top">&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classshark_1_1_iterative_n_n_query.html#af4917cb856b7b71d313d42978793e011">~IterativeNNQuery</a> ()</td></tr>
<tr class="memdesc:af4917cb856b7b71d313d42978793e011"><td class="mdescLeft">&#160;</td><td class="mdescRight">destroy the query object and its internal data structures  <br /></td></tr>
<tr class="separator:af4917cb856b7b71d313d42978793e011"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a8eadbf00c36ad200cbb2d75efed07c7b" id="r_a8eadbf00c36ad200cbb2d75efed07c7b"><td class="memItemLeft" align="right" valign="top">std::size_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classshark_1_1_iterative_n_n_query.html#a8eadbf00c36ad200cbb2d75efed07c7b">neighbors</a> () const</td></tr>
<tr class="memdesc:a8eadbf00c36ad200cbb2d75efed07c7b"><td class="mdescLeft">&#160;</td><td class="mdescRight">return the number of neighbors already found  <br /></td></tr>
<tr class="separator:a8eadbf00c36ad200cbb2d75efed07c7b"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:ac980e389bfdd03966ab9eee72491f520" id="r_ac980e389bfdd03966ab9eee72491f520"><td class="memItemLeft" align="right" valign="top">result_type&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classshark_1_1_iterative_n_n_query.html#ac980e389bfdd03966ab9eee72491f520">next</a> ()</td></tr>
<tr class="memdesc:ac980e389bfdd03966ab9eee72491f520"><td class="mdescLeft">&#160;</td><td class="mdescRight">find and return the next nearest neighbor  <br /></td></tr>
<tr class="separator:ac980e389bfdd03966ab9eee72491f520"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:ac55c632054e204acc14e0b554320d9a9" id="r_ac55c632054e204acc14e0b554320d9a9"><td class="memItemLeft" align="right" valign="top">std::size_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classshark_1_1_iterative_n_n_query.html#ac55c632054e204acc14e0b554320d9a9">queuesize</a> () const</td></tr>
<tr class="separator:ac55c632054e204acc14e0b554320d9a9"><td class="memSeparator" colspan="2">&#160;</td></tr>
</table>
<a name="details" id="details"></a><h2 class="groupheader">Detailed Description</h2>
<div class="textblock"><div class="compoundTemplParams">template&lt;class DataContainer&gt;<br />
class shark::IterativeNNQuery&lt; DataContainer &gt;</div><p>Iterative nearest neighbors query. </p>
<dl class="section user"><dt></dt><dd>The <a class="el" href="classshark_1_1_iterative_n_n_query.html" title="Iterative nearest neighbors query.">IterativeNNQuery</a> class (Iterative Nearest Neighbor Query) allows the nearest neighbors of a reference point to be queried iteratively. Given the reference point, a query is set up that returns the nearest neighbor first, then the second nearest neighbor, and so on. Thus, nearest neighbor queries are treated in an "online" fashion. The algorithm follows the paper (generalized to arbitrary space-partitioning trees):</dd></dl>
<dl class="section user"><dt></dt><dd>Strategies for efficient incremental nearest neighbor search. A. J. Broder. Pattern Recognition 23(1/2), pp 171-178, 1990.</dd></dl>
<dl class="section user"><dt></dt><dd>The algorithm is based on traversing a <a class="el" href="classshark_1_1_binary_tree.html" title="Super class of binary space-partitioning trees.">BinaryTree</a> that partitions the space into nested cells. The triangle inequality is applied to exclude cells from the search. Furthermore, candidate points are cached in a queue, such that subsequent queries profit from points that could not be excluded this way, but that did not turn out the be the (current) nearest neighbor.</dd></dl>
<dl class="section user"><dt></dt><dd>The tree must have a bucket size of one, but leaf nodes with multiple copies of the same point are allowed. This means that the space partitioning must be carried out to the finest possible scale.</dd></dl>
<p>The <a class="el" href="classshark_1_1_data.html" title="Data container.">Data</a> must be sotred in a random access container. This means that elements have O(1) access time. This is crucial for the performance of the tree lookup. When data is stored in a Data&lt;T&gt;, a View should be chosen as template parameter. </p>

<p class="definition">Definition at line <a class="el" href="_tree_nearest_neighbors_8h_source.html#l00082">82</a> of file <a class="el" href="_tree_nearest_neighbors_8h_source.html">TreeNearestNeighbors.h</a>.</p>
</div><h2 class="groupheader">Constructor &amp; Destructor Documentation</h2>
<a id="a02c6b80d059c5bd4964ed64a7420ede0" name="a02c6b80d059c5bd4964ed64a7420ede0"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a02c6b80d059c5bd4964ed64a7420ede0">&#9670;&#160;</a></span>IterativeNNQuery()</h2>

<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class DataContainer &gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="classshark_1_1_iterative_n_n_query.html">shark::IterativeNNQuery</a>&lt; DataContainer &gt;::IterativeNNQuery </td>
          <td>(</td>
          <td class="paramtype"><a class="el" href="classshark_1_1_binary_tree.html">tree_type</a> const *&#160;</td>
          <td class="paramname"><em>tree</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">DataContainer const &amp;&#160;</td>
          <td class="paramname"><em>data</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">value_type const &amp;&#160;</td>
          <td class="paramname"><em>point</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">inline</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<p>create a new query </p><dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">tree</td><td>Underlying space-partitioning tree (this is assumed to persist for the lifetime of the query object). </td></tr>
    <tr><td class="paramname">data</td><td>Container holding the stored data which is referenced by the tree </td></tr>
    <tr><td class="paramname">point</td><td>Point whose nearest neighbors are to be found. </td></tr>
  </table>
  </dd>
</dl>

<p class="definition">Definition at line <a class="el" href="_tree_nearest_neighbors_8h_source.html#l00094">94</a> of file <a class="el" href="_tree_nearest_neighbors_8h_source.html">TreeNearestNeighbors.h</a>.</p>

<p class="reference">References <a class="el" href="classshark_1_1_binary_tree.html#a8d5379344624257a1c2950d4e64ab8c0">shark::BinaryTree&lt; InputT &gt;::hasChildren()</a>, <a class="el" href="classshark_1_1_binary_tree.html#a456c9994792021b1bb2557cad4ab7a3e">shark::BinaryTree&lt; InputT &gt;::isLeft()</a>, <a class="el" href="classshark_1_1_binary_tree.html#ae20385cf5cf85d7168db9b3fcf411c47">shark::BinaryTree&lt; InputT &gt;::left()</a>, and <a class="el" href="classshark_1_1_binary_tree.html#ae5167564abb964d90da01897693a5768">shark::BinaryTree&lt; InputT &gt;::right()</a>.</p>

</div>
</div>
<a id="af4917cb856b7b71d313d42978793e011" name="af4917cb856b7b71d313d42978793e011"></a>
<h2 class="memtitle"><span class="permalink"><a href="#af4917cb856b7b71d313d42978793e011">&#9670;&#160;</a></span>~IterativeNNQuery()</h2>

<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class DataContainer &gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="classshark_1_1_iterative_n_n_query.html">shark::IterativeNNQuery</a>&lt; DataContainer &gt;::~<a class="el" href="classshark_1_1_iterative_n_n_query.html">IterativeNNQuery</a> </td>
          <td>(</td>
          <td class="paramname"></td><td>)</td>
          <td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">inline</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>destroy the query object and its internal data structures </p>

<p class="definition">Definition at line <a class="el" href="_tree_nearest_neighbors_8h_source.html#l00122">122</a> of file <a class="el" href="_tree_nearest_neighbors_8h_source.html">TreeNearestNeighbors.h</a>.</p>

</div>
</div>
<h2 class="groupheader">Member Function Documentation</h2>
<a id="a8eadbf00c36ad200cbb2d75efed07c7b" name="a8eadbf00c36ad200cbb2d75efed07c7b"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a8eadbf00c36ad200cbb2d75efed07c7b">&#9670;&#160;</a></span>neighbors()</h2>

<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class DataContainer &gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">std::size_t <a class="el" href="classshark_1_1_iterative_n_n_query.html">shark::IterativeNNQuery</a>&lt; DataContainer &gt;::neighbors </td>
          <td>(</td>
          <td class="paramname"></td><td>)</td>
          <td> const</td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">inline</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>return the number of neighbors already found </p>

<p class="definition">Definition at line <a class="el" href="_tree_nearest_neighbors_8h_source.html#l00129">129</a> of file <a class="el" href="_tree_nearest_neighbors_8h_source.html">TreeNearestNeighbors.h</a>.</p>

</div>
</div>
<a id="ac980e389bfdd03966ab9eee72491f520" name="ac980e389bfdd03966ab9eee72491f520"></a>
<h2 class="memtitle"><span class="permalink"><a href="#ac980e389bfdd03966ab9eee72491f520">&#9670;&#160;</a></span>next()</h2>

<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class DataContainer &gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">result_type <a class="el" href="classshark_1_1_iterative_n_n_query.html">shark::IterativeNNQuery</a>&lt; DataContainer &gt;::next </td>
          <td>(</td>
          <td class="paramname"></td><td>)</td>
          <td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">inline</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

<p>find and return the next nearest neighbor </p>

<p class="definition">Definition at line <a class="el" href="_tree_nearest_neighbors_8h_source.html#l00134">134</a> of file <a class="el" href="_tree_nearest_neighbors_8h_source.html">TreeNearestNeighbors.h</a>.</p>

<p class="reference">References <a class="el" href="_exception_8h.html#adce1f80097c69010f5eab2618fa2e971">SHARK_RUNTIME_CHECK</a>.</p>

<p class="reference">Referenced by <a class="el" href="classshark_1_1_tree_nearest_neighbors.html#a93240024a5a340943a32c46c88347648">shark::TreeNearestNeighbors&lt; InputType, LabelType &gt;::getNeighbors()</a>.</p>

</div>
</div>
<a id="ac55c632054e204acc14e0b554320d9a9" name="ac55c632054e204acc14e0b554320d9a9"></a>
<h2 class="memtitle"><span class="permalink"><a href="#ac55c632054e204acc14e0b554320d9a9">&#9670;&#160;</a></span>queuesize()</h2>

<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class DataContainer &gt; </div>
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">std::size_t <a class="el" href="classshark_1_1_iterative_n_n_query.html">shark::IterativeNNQuery</a>&lt; DataContainer &gt;::queuesize </td>
          <td>(</td>
          <td class="paramname"></td><td>)</td>
          <td> const</td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">inline</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<p>return the size of the queue, which is a measure of the overhead of the search </p>

<p class="definition">Definition at line <a class="el" href="_tree_nearest_neighbors_8h_source.html#l00169">169</a> of file <a class="el" href="_tree_nearest_neighbors_8h_source.html">TreeNearestNeighbors.h</a>.</p>

</div>
</div>
<hr/>The documentation for this class was generated from the following file:<ul>
<li>include/shark/Algorithms/NearestNeighbors/<a class="el" href="_tree_nearest_neighbors_8h_source.html">TreeNearestNeighbors.h</a></li>
</ul>
</div><!-- contents -->
</div>
</body>
</html>
